/***
 * Cache implementation for L1/L2/L3 caches
 * 
 * Caches are not implemented in a coherent manner, therefor in order
 * to simulate a coherent cache (if so desired), the MMU will need to
 * fake the operatings normally performed to ensure cache integrity.
 **/

// A note about alignment:
// Where possible elements of this emulator go out of their way to
// support unaligned access both for portability and in case it should
// be needed by an add-on (for example one that initializes memory to
// emulate the existance of a ROM module).  In the cache implementation
// we could not think of a friendly way to respond to unaligned access
// (the MIPS cache just wasn't made that way), nor could we think of
// any reason it would be useful.  Therefore the following cache
// implementation will not allow unaligned access, please bear this
// in mind if you plan to write an add-on that will need to inspect
// the contents of the caches as well as the RAM.

typedef sim_addr		cache_addr;

// Cache geometry is derived mostly from the style of the Config regs
 struct cache_geometry {
	uint8_t		idx;				// index positions in cache = 64x2^(idx)
	uint8_t		line;				// line size = 2x2^(line)
	uint8_t		assoc;				// associativity of cache = assoc+1
 };

typedef struct cache_geometry	cache_geom;

struct cache_line {
	// tag: |    ADDRESS TAG    | Unused | Locked | Dirty | Valid |
	cache_addr	tag;				// client facing cache api exposed through tag
	sim_size	lru;				// Least recently used tag to help decide victim for eviction
	uint8_t		writing;			// busy flag in case a line is being written to memory
	uint8_t		bytes[];			// bytes in cache
};
typedef struct cache_line cache_line;

struct cache {
	cache_geom		geom;			// Cache geometry for Config
	sim_size		access;			// count number of accesses to cache
									// this field is used to calculate LRU value
	cache_addr		ways;			// associativity of cache'

	// way_mask, way_shift are used to make reading indices easier:
	// index: | Unused |      Way      | Index | Byte Offset |
	//                 |<-  way_mask ->|<------------way_shift

	cache_addr		way_mask;
	cache_addr		way_shift;
	
	// the following fields are useful for reading tags and addresses:
	// address: |      TAG      |     INDEX     |     BYTES     |
	//          |<- tag_mask  ->|<-index_mask ->|<- byte_mask ->|
	//                          |<--------------------index_shift

	// tag:     |     TAG     | Unused | Locked | Dirty | Valid |
	//          |<-tag_mask ->|

	cache_addr		tag_mask;		// mask the part of an address used for tagging cache lines
	cache_addr		tag_shift;		// the number of bits to shift a tag right (diagnostic)
	cache_addr		index_mask;		// mask the part of an address used as an index into the cache
	cache_addr		index_shift;	// the number of bits to shift right to get the index
	cache_addr		byte_mask;		// mask the part of an address used as a byte offset into a cache line

	// these two fields are useful for allocating and freeing
	// cache lines as well as for checking input parameters

	cache_addr		bytes;			// number of bytes in a cache line
	cache_addr		indices;		// number of indices in the cache
	
	cache_line		***lines;		// cache lines for cache, stored as follows:
									// pointer to an array of pointers to arrays of cache lines
									// each array represents an associative set
};

#define CACHE_VALID		0x1		// cache line is valid
#define CACHE_DIRTY		0x2		// cache line is dirty
#define CACHE_LOCKED	0x4		// cache line is locked

#define idx_to_addr(c, t, i)	(((c)->tag_mask & (t)) | ((c)->index_mask & (i)))
#define addr_to_idx(c, a)		((c)->index_mask & (a))
#define addr_to_tag(c, a)		((c)->tag_mask & (a))

/****
 * create_cache - Allocate space for a new cache
 *
 * c		- A cache structure with its geom field filled with the desired geometry
 *
 * Returns E_OKAY on success, E_INVALID if geom.line is not a multiple of sizeof(sim_size),
 * and E_SYS_NOMEM if space could not be allocated for the cache
 **/
cache_error
create_cache(CACHE *c);

/****
 * destroy_cache - Deallocate a fully initialized cache
 *
 * c		- The cache to deallocate
 *
 * Returns E_OKAY
 **/
cache_error
destroy_cache(CACHE *c);

/****
 * cache_read_index - Read a value stored at a given cache index
 *
 * c		- Cache to read from
 * index	- Index to read (see structure above for format)
 * tag		- If not null, will be filled with tag field of cache line
 * len		- Length of read
 * buf		- If not null, buffer to read into
 * 
 * Returns E_OKAY on success, E_INVALID if read would run off the end
 * of a cache line
 **/
cache_error
cache_read_index(	CACHE *c,
					cache_addr index,
					cache_addr *tag,
					uint8_t len,
					uint8_t *buf);

/****
 * cache_write_index - Write a value to a given cache index
 *
 * c		- Cache to write to
 * index	- Index to write (see structure for format)
 * tag		- If not null will be written to the tag field of the line
 * len		- Length to write
 * buf		- If not null, buffer to write from
 *
 * Returns E_OKAY on success, E_INVALID if write would run off the end of a cache line, 
 * and E_CACHE_BUSY if the cache line is currently being written back to memory
 **/
cache_error
cache_write_index(	CACHE *c,
					cache_addr index,
					const cache_addr *tag,
					uint8_t len,
					const uint8_t *buf);

/****
 * cache_read_addr - Read a value at a given cache address (on cache hit)
 *
 * c		- Cache to read from
 * addr		- The address to search the cache for
 * tag		- If not null will contain the tag of the cache line if result is a cache hit
 * len		- Bytes to read
 * buf		- If not null buffer to read into
 *
 * Returns E_CACHE_HIT on success, E_CACHE_MISS if addr not in cache, and E_INVALID if read
 * would run off the end of a cache line
 **/
cache_error
cache_read_addr(	CACHE *c,
					cache_addr addr,
					cache_addr *tag,
					uint8_t len,
					uint8_t *buf);

/****
 * cache_write_addr - Write a value to a given cache address (on cache hit)
 *
 * c		- Cache to write to
 * addr		- Address to search cache for
 * tag		- If not null will be written to cache tag on cache hit
 * len		- Length of write
 * buf		- Buffer to write from
 *
 * Will set the dirty flag if the tag is not changed.
 * Returns E_CACHE_HIT on success, E_CACHE_MISS if addr not in cache, E_INVALID if write would
 * run off the end of a cache line, E_CACHE_BUSY if line is being written back
 **/
cache_error
cache_write_addr(	CACHE *c,
					cache_addr addr,
					const cache_addr *tag,
					uint8_t len,
					const uint8_t *buf);

/****
 * cache_insert_addr - Insert an address into the cache
 *
 * c		- Cache to insert into
 * addr		- The address to insert
 * buf		- Buffer to insert from, must be big enough to fill a cache line
 * wb		- If not null if there is no clean cache line wb will contain the address of a line to write
 *			  back to the cache to free up space, only valid on E_CACHE_WRITEBACK
 *
 * Returns E_OKAY on successful insert, E_CACHE_HIT if address already in cache, E_INVALID on bad
 * alignment, E_CACHE_BUSY if all lines are busy, and E_CACHE_FULL if all lines are locked
 **/
cache_error
cache_insert_addr(	CACHE *c,
					cache_addr addr,
					const uint8_t *buf,
					cache_addr *wb);

/****
 * cache_open_writeback - Begin writing back a cache line, locks line
 *
 * c		- Cache to writeback from
 * addr		- Address to write back
 * buf		- If not null will be filled with entire cache line
 *
 * Returns E_OKAY on success, E_CACHE_MISS if addr not in cache, E_INVALID on bad alignment, and
 * E_CACHE_CLEAN if cache is already clean
 **/
cache_error
cache_open_writeback(	CACHE *c,
						cache_addr addr,
						uint8_t *buf);

/****
 * cache_close_writeback - End writing back a cache line, unlocks line, clears dirty flag
 *
 * c		- Cache for writeback
 * addr		- Address to unlock
 *
 * Returns E_OKAY on success, E_CACHE_MISS if addr not in cache and E_INVALID on bad alignment, clears
 * busy and dirty flags on success
 **/
cache_error
cache_close_writeback(	CACHE *c,
						cache_addr addr);

/****
 * cache_abort_writeback - Abort writing back a line, unlocks line without clearing dirty flag
 *
 * c		- Cache for writeback
 * addr		- Address to unlock
 * Returns E_OKAY on success, E_CACHE_MISS if addr not in cache and E_INVALID on bad alignment, clears
 * busy flag on success
 **/
cache_error
cache_abort_writeback(	CACHE *c,
						cache_addr addr);

